Masala #0653

Xotira 10 MB Vaqt 300 ms Qiyinchiligi 20 %
14

  

Kvadrat

Dekart koordinatalar tizimida 4 ta d1, d2, d3, d4 (di = (x,y)) nuqta beriladi.

Bu nuqtalardan kordinata o'qlariga paralel bolgan to'g'ri tortburchak bolishi kafolatlanadi. Siz istalgan d= (x, y) nuqtani (x,y+1), (x,y−1), (x+1,y) va (x−1,y) nuqtalardan biriga siljitishingiz mumkin boladi. Vazifangiz OX va OY oqlariga paralel bo'lgan kvadrat hosil qilish uchun minimum urinishlarda sonini topishdan iborat.

Berilgan nuqtalar 1 bir xil bo'lmasligi taminlanadi.


Kiruvchi ma'lumotlar:

INPUT.TXT Kiritish faylida 1-qatorda bitta butun son t (1 ≤ t ≤ 104) - test soni.

har bir test uchun 4ta (di = (x,y)) nuqta kordinatalari kiritiladi.Har bir satrda ikkita butun son x va y (0 ≤ x,y ≤ 109).


Chiquvchi ma'lumotlar:

OUTPUT.TXT Chiqish faylida Kvadrat olish uchun zarur bo'lgan minimal qadamlar sonini har bir test uchun alohida qatorlarda chop eting.


Misollar
# input.txt output.txt
1
3
0 2
4 2
2 0
2 4
1 0
2 0
4 0
6 0
1 6
2 2
2 5
4 1
8
7
5
Izoh:

1-test uchun minimal urinishlar soni quydagicha bo'lishi mumkin:

Har bir nuqta ikki marta siljiydi, shuning uchun natija 2+2+2+2=8.
Ikkinchi to'plamda optimal javoblardan biri quyida tasvirlangan:

Natija : 3+1+0+3=7.
Uchinchi to'plamda optimal yurishlardan biri quyida tasvirlangan:

Natija : 1+1+2+1=5.

 

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin